Problem

Time limit : 2sec / Memory limit : 256MB

将$1-n$顺序加入双端队列（每次可加头可加尾），再删除（每次可删头可删尾），求有多少种删除序列，使得$1$是第$k$个被删的。

传送门

Solution

考虑合法的删除序列，发现满足如下的性质：

第$k$个是$1$
前$k-1$个元素能拆分成两个单调下降序列
第$k$个后的元素每个位置都大于等于后缀最大值或小于等于后缀最小值
前$k-1$个元素拆分出的单调下降序列其中一个的最小值大于等于第$k$个后的元素的最大值

思考怎么构造这个删除序列

先考虑后$n-k-1$个数，这些数一定是由一个单调的队列每次弹出头或尾来构成的，只要我们确定前$k-1$个数，就可以得出这个单调的队列能构成的后$n-k-1$个数的方案，就是$2^{n-k-1}$

问题来了，我们应该如何确定前$k-1$个数，使其满足第二条性质呢？

设$f_{i,j}$表示，前$k-1$个数中，已确定了$i$个数，在已经确定的数中的最小值为$j$。

如果加进第一个单调序列，那么第二个单调序列就要满足第4条性质

新加一个数时，加进第一个单调序列，显然加入的数就要小于$j $

这时$f_{i,j}$转移到$f_{i+1,k}(k<j)$

如果加进第二个单调序列，则加入的数就要是当前没加的数中最大的

这时$f_{i,j}$转移到$f_{i+1,j}$

Code:

Click to show/hide the code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
const long long mo = 1e9 + 7;
const int MAXN = 3000 + 10;
using namespace std;
int n, k;
long long ans, po[MAXN], f[MAXN][MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	po[0] = 1;
	for (register int i = 1; i <= n; i++) po[i] = po[i - 1] * 2 % mo;
	for (register int i = n; i >= 2; i--) f[1][i] = 1;
	for (register int i = 1; i < k - 1; i++)
	{
		register long long sum = f[i][n - i + 1];
		for (register int j = n - i; j >= 2; j--)
		{
			sum = (sum + f[i][j]) % mo;
			f[i + 1][j] = (f[i + 1][j] + sum) % mo;
		}
	}
	for (register int j = 2; j <= n - k + 2; j++) ans = (ans + f[k - 1][j]) % mo;
	if (k == 1) ans = 1;
	if (n - 1 - k < 0) cout << ans;
	else cout << ans * po[n - 1 - k] % mo;
	return 0;
}